package com.msb.class01;

/**
 * @Auther: jiudianliu
 * @Date: 2023/12/29 - 12 - 29 - 15:45
 * @Description: com.msb.a
 * @version: 1.0
 * 选择排序  冒泡排序  插入排序
 */
public class ClassOne {

    /*
    *  arr 数组中 a位置和b位置的数值互换  （用第三方）
    * */
    public static void swapIndex( int arr[] , int a , int b ){
        int emp = arr[a] ;
        arr[a] = arr[b] ;
        arr[b] = emp ;
/*        arr[a] = arr[a] ^ arr[b] ;
        arr[b] = arr[a] ^ arr[b] ;
        arr[a] = arr[a] ^ arr[b] ;*/

    }

    // 打印数组中的每个数
    public static void printIndex(int arr[]){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println( );
    }


    /*
    *  选择排序
    *  位置0~arr.length-1  相比，最小的移到0
    *  位置1~arr.length-1  相比，最小的移到1
    *  位置2~arr.length-1  相比，最小的移到2
    *  位置i~arr.length-1  相比，最小的移到i
    * */
    public static void selectSort( int arr[] ){
        // 确定边界
        if ( arr == null || arr.length < 2){
            return;
        }
        int N = arr.length-1 ;
        // 控制大范围
        for (int i = 0 ; i <= N ; i++){
            // 设置一个临时位置变量，最开始在i位置，之后谁小到谁的位置
            int min = i ;
            // j是挨个往下比较的位置控制变量，最开始是i的下一个，逐次递加
            for (int j = i + 1 ; j <= N ; j++){
                // 三目运算   如果j位置上的数小于min位置的数，那么min就到i位置，否则不变
                min = arr[j] < arr[min] ? j : min ;
            }
            // 找出最小的min位置，与i位置交换
            swapIndex(arr , i , min);
        }
    }

    /*
    * 冒泡排序
    * 0-arr.length-1 之间 谁大谁往右
    * 0-arr.length-2 之间 谁大谁往右
    * 0-arr.length-3 之间 谁大谁往右
    * 0-arr.length-N 之间 谁大谁往右
    * */
    public static void bubbleSort( int arr[]) {
        // 边界
        if ( arr == null || arr.length < 2 ) {
            return;
        }
        int end = arr.length-1 ;
        // 控制大范围  逐渐递减
        for (int i = end ; i >= 0 ; i--){
            for (int second = 1 ; second <= end ; second++){
                // 当 second=1 时，
                // 那么就会跟second前一个位置比较，
                // 如果前一个位置大于当前位置，交换
                if (arr[second-1] > arr[second]){
                    swapIndex( arr , second-1 , second);
                }
            }
        }
    }


    /*
    * 插入排序       大数往后放
    * 0~0范围上有序
    * 0~1范围上有序
    * 0~2范围上有序
    * 0~3范围上有序
    * 0~4范围上有序
    * 0~arr.length-1范围上有序
    * */
    public static void insertSort(int arr[]){
        if ( arr == null || arr.length < 2 ){
            return;
        }
        int N = arr.length - 1;
        // 控制大范围
        for (int i = 1 ; i <= N ; i++){
            // 开始 新数在i位置
            for (int newIndex = i ;
                 // 跳出循环的条件：新数的左边一位有数 并且 左边的数大于右边的树
                 newIndex-1 >= 0  && arr[newIndex-1] > arr[newIndex] ;
                 newIndex-- ){
                // 俩数交换
                swapIndex( arr , newIndex-1 , newIndex);
            }
        }
    }


    public static void main(String[] args) {
        int arr[] = {2,4,5,6,1,2,8,6,3,9} ;
        printIndex(arr);
        selectSort(arr);
        bubbleSort(arr);
        insertSort(arr);
        printIndex(arr);
    }
}
